Coudenhove-Kalergi merupakan anak lelaki kedua Heinrich von Coudenhove-Kalergi (1859–1906), seorang bangsawan dan diplomat Austria-Hungary. Ibu beliau ialah Mitsuko Aoyama (1874–1941). Ayah beliau, yang mahir bertutur dalam enam belas bahasa dan menganuti pengembaraan sebagai satu-satunya cara untuk memanjangkan nyawa tetapi meninggal berumur empat puluhan, telah dari awal meninggalkan kerjaya dalam pentadbiran diplomatik Austria yang membawa beliau ke Athens, Kustantiniyah, Rio de Janeiro dan Tokyo, untuk membakti dirinya kepada pengajian dan penulisan.

Ibu bapa Coudenhove-Kalergi menemui kali pertama bila ibu beliau membantu sang diplomat Austria-Hungary selepas dia terjatuh dari seekor kuda sewaktu menunggang di Jepun. Dalam pengulasan akan pasangan mereka, Whittaker Chambers menghuraikan bakal pengusul Se-Eropah sebagai "hampir pertubuhan Se-Eropah sendiri". Dia menjelaskan "Sang Coudenhove adalah sebuah keluarga kaya Flemish yang berlari ke Austria semasa Revolusi Perancis. Sang Kalergis adalah sebuah keluarga kaya Yunani dari Kriti. Selanjutnya keturunan tersebut telah disilang bersama orang Poland, Norway, Baltik, Perancis dan Jerman, tetapi kerana keluarga-keluarga berikut sifat pemilih dan juga kosmopolitan, kacukan tersebut agak berjaya secara konsisten."[6] Rumpun keluarga Kalergis mengatakan keturunannya dari golongan diraja Byzantium melalui kebangsawanan Venice, bersambung dengan kerabat Phokas. Pada 1300, leluri Coudenhove-Kalergi, Alexios Phokas-Kalergis menandatangani perjanjian yang membuat Kriti sebuah jajahan Venice.

Semasa dia membesar, bonda Coudenhove-Kalergi membacakan kepadanya Momotarō dan kisah dongeng Jepun lain.[7]